import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 雷世雄爸爸
 * Date: 2021-11-07
 * Time: 19:15
 */
class TreeNode {
    public char val;
    public TreeNode left;//null
    public TreeNode right;//null

    public TreeNode(char val) {
        this.val = val;
    }
}
public class MyTreeNode {
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
//    前序遍历的遍历思路
    List<Character>list=new ArrayList<>();
    public List<Character>qianxubainli(TreeNode root){


        if (root==null)return null;
        list.add(root.val);
        qianxubainli(root.left);
        qianxubainli(root.right);
        return list;
    }
//    前序遍历的子问题思路
    /**
     * 前序遍历，把遍历结果存储在，List当中。
     * 子问题：
     * @param root
     * @return
     */
public List<Character> preorderTraversal2(TreeNode root) {
    List<Character> list = new ArrayList<>();
    if(root == null) return list;
    list.add(root.val);

    List<Character> leftTree = preorderTraversal2(root.left);
    list.addAll(leftTree);

    List<Character> rightTree =preorderTraversal2(root.right);
    list.addAll(rightTree);

    return list;
}

//    中序遍历的遍历思路
    public void zhongxubianli2(TreeNode root){
        if (root==null)return;
        zhongxubianli2(root.left);
        System.out.print(root.val+" ");
        zhongxubianli2(root.right);
    }
//    后序遍历的遍历思路
    public void houxubianli(TreeNode root){
    if (root==null)return;
    houxubianli(root.left);
    houxubianli(root.right);
        System.out.print(root.val+" ");
    }
//    二叉树的层序遍历
void levelOrderTraversal(TreeNode root){
    if(root==null)return;
    Queue <TreeNode>queue=new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
        TreeNode cur =queue.poll();
        System.out.print(cur.val+" ");
        if (cur.left!=null){
            queue.offer(cur.left);
        }
        if (cur.right!=null){
            queue.offer(cur.right);
        }
    }
}
//    求节点个数
    int size =0;
    public int getSize1(TreeNode root){
    if (root==null)return 0;
    size++;
    getSize1(root.left);
    getSize1(root.right);
        return size;
    }
    public int getSize2(TreeNode root){
        if (root==null)return 0;
        return getSize2(root.left)+getSize2(root.right)+1;
    }
//    求叶子节点个数
//   遍历思路
    static int leafsize=0;
    public int getLeafsize1(TreeNode root){
       if (root==null)return 0;
       if (root.left==null&&root.right==null){
           leafsize++;
       }else{
           getLeafsize1(root.left);
           getLeafsize1(root.right);
       }
       return leafsize;
    }
//    子问题思路
    public int getLeafsize2(TreeNode root){
        if (root==null)return 0;
        if (root.left==null&&root.right==null){
            return 1;
        }else{
            return getLeafsize2(root.left)+getLeafsize2(root.right);
        }
    }
//    求第K层节点的个数
//    子问题思路
    public int getKLevelSize(TreeNode root,int k){
        if (root==null)return 0;
        if (k==1){
            return 1;
        }else {
            return getKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1);
        }
    }
//    查找结点
//    子问题思路
    public TreeNode find(TreeNode root,char val){
        if (root==null){
            return null;
        }
        if (root.val==val){
            return root;
        }
        TreeNode ret=find(root.left,val);
        if (ret!=null){
            return ret;
        }

        ret=find(root.right,val);
        if (ret!=null)return ret;
        return null;
    }
}

